
#ifndef ___FANXES_PROG_COMMON_H_
#define ___FANXES_PROG_COMMON_H_

#include <time.h>

#define RAND_SEED srand( (unsigned)time(0) )
#define CLOCK_DECLARE float _fx_clock_msec; \
    clock_t _fx_clock_start, _fx_clock_finish
#define CLOCK_START _fx_clock_start = clock()
#define CLOCK_FINISH _fx_clock_finish = clock()
#define CLOCK_OVERLAP_MS (_fx_clock_finish - _fx_clock_start) / CLK_TCK * 1000

#define MAXER( x, y ) (x) > (y) ? (x) : (y)
#define MINER( x, y ) (x) < (y) ? (x) : (y)

#define COLOR_DEFAULT 0x0F
#define FG_GRAY 0x08
#define FG_BLUE 0x09
#define FG_GREEN 0x0A
#define FG_BLUE_GREEN 0x0B
#define FG_RED 0x0C
#define FG_CYAN 0x0D
#define FG_YELLOW 0x0E
#define FG_WHITE 0x0F

#define PROG_PAUSE getchar()
#define PROG_BANNER ConSetColor( FG_GRAY << 4 ); \
    printf( "                                                       \n" ); \
    ConSetColor( COLOR_DEFAULT )

// ---- common

void ConGotoXY( int x, int y );
int ConGetColor();
void ConSetColor( int color );
void ConGetCurPos( int &x, int &y );

int RandomInt( int left = 0, int right = 2 )
{
    // [0..x]
    // right - left = x - 0;
    int tmp = rand() % (right - left);

    return tmp + left;
}

template<class T>
int Max( T a[], int n )
{
    // Locate the largest element in a[0:n-1].
    int pos = 0;
    for ( int i = 1; i < n; i++ )
        if ( a[pos] < a[i] )
            pos = i;

    return pos;
}

template<class T>
bool Max( T a[], int n, int& min, int& max )
{
    if ( n <  1 ) return false;

    min = max = 0;
    for ( int i = 1; i < n; i++ ) {
        if ( a[min] > a[i] ) min = i;
        if ( a[max] < a[i] ) max = i;
    }
}

template<class T>
inline void Swap( T& a, T& b )
{
    // Swap a and b.
    T temp = a; a = b; b = temp;
}



// ---- sort

template<class T>
void SelectionSort( T a[], int n )
{
    // Sort the n elements a[0:n-1].
    for ( int size = n; size > 1; size-- ) {
        int j = Max( a, size );
        Swap( a[j], a[size - 1] );
    }
}

template<class T>
void InsertSort( T a[], int n )
{
    // Sort the n elements a[0:n-1].
    for ( int i = 1; i < n; i++ ) {
        T t = a[i];
        int j;
        for ( j = i - 1; j >= 0 && t < a[j]; j-- )
            a[j+1] = a[j];
        a[j+1] = t;
    }
}


// ---- search

template<class T>
void SequentialSearch( T a[], const T& x, int n )
{
    int i;
    a[n] = x;

    for ( i = 0; a[i] != x; i++ );

    if ( i == n ) return -1;

    return i;
}

template<class T>
void BinarySearch( T a[], const T& x, int n )
{
    int left = 0;
    int right = n - 1;

    while( left <= right ) {
        int mid = (left + right)/2;

        if ( x == a[mid]) return mid;

        if ( x > a[mid] ) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1;
}

#endif // ___FANXES_PROG_COMMON_H_

